package LeetCode;

import java.util.Arrays;

public class LC_564_FindtheClosestPalindrome {

    public static void main(String[] args) {

    }

    public class Solution {

        public String nearestPalindromic(String n) {
            Long num = Long.parseLong(n);
            Long big = findBigPalindrome(num + 1);
            Long small = findSmallPalindrome(num - 1);
            return (big - num) < (num - small) ? String.valueOf(big) : String.valueOf(small);
        }

        Long findBigPalindrome(Long num) {
            String nStr = String.valueOf(num);
            char[] c = nStr.toCharArray();
            int len = c.length;
            char[] target = Arrays.copyOf(c, len);
            for (int i = 0; i < len / 2; i++) {
                target[len - 1 - i] = c[i];
            }
            for (int i = 0; i < len; i++) {
                if (c[i] < target[i]) {
                    return Long.parseLong(String.valueOf(target));
                } else if (c[i] > target[i]) {
                    for (int j = (len - 1) / 2; j >= 0; j--) {
                        if (++target[j] > '9')
                            target[j] = '0';
                        else
                            break;
                    }
                    for (int k = 0; k < len / 2; k++) {
                        target[len - 1 - k] = target[k];
                    }
                    return Long.parseLong(String.valueOf(target));
                }
            }
            return Long.parseLong(String.valueOf(target));
        }

        Long findSmallPalindrome(Long num) {
            String nStr = String.valueOf(num);
            char[] c = nStr.toCharArray();
            int len = c.length;
            char[] target = Arrays.copyOf(c, len);
            for (int i = 0; i < len / 2; i++) {
                target[len - 1 - i] = c[i];
            }
            for (int i = 0; i < len; i++) {
                if (c[i] > target[i]) {
                    return Long.parseLong(String.valueOf(target));
                } else if (c[i] < target[i]) {
                    for (int j = (len - 1) / 2; j >= 0; j--) {
                        if (--target[j] < '0')
                            target[j] = '9';
                        else
                            break;
                    }
                    if (target[0] == '0') {
                        char[] tar2 = new char[len - 1];
                        Arrays.fill(tar2, '9');
                        return Long.parseLong(String.valueOf(tar2));
                    }
                    for (int k = 0; k < len / 2; k++) {
                        target[len - 1 - k] = target[k];
                    }
                    return Long.parseLong(String.valueOf(target));
                }
            }
            return Long.parseLong(String.valueOf(target));
        }
    }


    public class Solution_2 {

        String mirroring(String s) {
            String x = s.substring(0, (s.length()) / 2);
            return x + (s.length() % 2 == 1 ? s.charAt(s.length() / 2) : "") + new StringBuilder(x).reverse().toString();
        }

        public String nearestPalindromic(String n) {
            if (n.equals("1")) return "0";
            String a = mirroring(n);
            long diff1;
            diff1 = Math.abs(Long.parseLong(n) - Long.parseLong(a));
            if (diff1 == 0) diff1 = Long.MAX_VALUE;
            StringBuilder s = new StringBuilder(n);
            int i = (s.length() - 1) / 2;
            while (i >= 0 && s.charAt(i) == '0') {
                s.replace(i, i + 1, "9");
                i--;
            }
            if (i == 0 && s.charAt(i) == '1') {
                s.delete(0, 1);
                int mid = (s.length() - 1) / 2;
                s.replace(mid, mid + 1, "9");
            } else
                s.replace(i, i + 1, "" + (char) (s.charAt(i) - 1));
            String b = mirroring(s.toString());
            long diff2 = Math.abs(Long.parseLong(n) - Long.parseLong(b));
            s = new StringBuilder(n);
            i = (s.length() - 1) / 2;
            while (i >= 0 && s.charAt(i) == '9') {
                s.replace(i, i + 1, "0");
                i--;
            }
            if (i < 0)
                s.insert(0, "1");
            else
                s.replace(i, i + 1, "" + (char) (s.charAt(i) + 1));
            String c = mirroring(s.toString());
            long diff3 = Math.abs(Long.parseLong(n) - Long.parseLong(c));
            if (diff2 <= diff1 && diff2 <= diff3)
                return b;
            if (diff1 <= diff3 && diff1 <= diff2)
                return a;
            else
                return c;
        }
    }

}